from numpy.core.numeric import Infinity

# Version 1.1
#
# Changes in 1.1: 
# In order to optimize the list handling I implemented the location id (lid) attribute.
# This will make the all list serahces to become extremely more optimized.
WAIT_COST=1
class Path:
    def __init__(self,nodes, totalCost, totalTime):
        self.nodes = nodes;
        self.totalCost = totalCost;
        self.totalTime=totalTime
    def getNodes(self): 
        return self.nodes    

    def getTotalMoveCost(self):
        return self.totalCost
    def getTotalTime(self):
        return self.totalTime
    def __str__(self):
        s=""
        for n in self.nodes:
            s+=str(n)
        return s
    def __eq__(self,other):
        return self.getNodes() == other.getNodes()

class Node:
    def __init__(self,time,location,mCost,lid,parent=None):
        self.location = location # where is this node located
        self.mCost = mCost # total move cost to reach this node
        self.parent = parent # parent node
        self.score = 0 # calculated score for this node
        self.lid = lid # set the location id - unique for each location in the map
        self.time = time # set the current time

    def __eq__(self, n):
        if n.lid == self.lid and n.time == self.time:
            return 1
        else:
            return 0
    def __str__(self):
        return "{["+str(self.location.x) +","+ str(self.location.y)+"],"+str(self.time)+"}"    
    def __hash__(self):
        return hash(self.lid)+hash(self.time)                

class Lid:
    def __init__(self,source,target):
        self.source = source
        self.target = target
        self.width = 3
    
    def __eq__(self,n):
        return (self.source == n.source and self.target == n.target 
                or self.source == n.target and self.target == n.source)
    
    def __hash__(self):
        return hash(self.source) + hash(self.target)
    
    def __str__(self):
        source = self.source
        sy = source/self.width
        sx = source % self.width 
        target = self.target
        if target == -1:
            ty = tx = '.'
        else:             
            ty = target/self.width
            tx = target % self.width
        return str(sx)+","+str(sy)+ "->" + str(tx)+","+str(ty)
      
        
class EdgeNode(Node):
    def __init__(self,location,mCost,lid,n1,n2,time,parent=None):
        self.location = location
        self.mCost = mCost
        self.s = n1
        self.t = n2
        self.lid=lid
        self.time=time
        self.score=0
                
    def __str__(self):
        return "{"+str(self.s)+"->"+str(self.t)+","+str(self.time)+"}"


def isConflicted(node , conflict):
    if conflict is None:
        return False
    return conflict.lid == node.lid and conflict.time == node.time    


def getMaxBid(bids, lid, time, agentId):
    if lid not in bids.keys():
        return 0
    if time>len(bids[lid])-1:
        return 0
    epsilon=0.0001
    bidList = bids[lid][time]
    maxBids=[]
    maxBid=0
    for _agent in bidList.keys():
        if bidList[_agent]==maxBid:            
            maxBids.append((_agent,bidList[_agent]))            
        elif bidList[_agent]>maxBid:                 
            maxBids=[(_agent,bidList[_agent])]      
            maxBid=bidList[_agent]
    if len(maxBids)<=1:
        return maxBid
    else:
        if agentId == maxBids[0][0]: #for first agent its best
            return maxBid
        result=maxBid + epsilon
        return result #other agents tie break

    
class AStar:
    def __init__(self,maphandler):
        self.mh = maphandler
                
    def _getBestOpenNode(self):
        bestNode = None        
        for n in self.on:
            if not bestNode:
                bestNode = n
            else:
                if n.score<=bestNode.score:
                    bestNode = n
        return bestNode

    def _tracePath(self,n):
        nodes = [];
        totalCost = n.mCost;        
        p = n.parent;
        nodes.insert(0,n);               
        while 1:
            if p.parent is None: 
                break
            nodes.insert(0,p)
            p=p.parent        
        return Path(nodes,totalCost,n.time)


    def generateWaitNode(self, node):
        if isinstance(node, EdgeNode):
            return None  
        wait = self.mh.getNode(node.location)
        wait.time = node.time + 1
        wait.mCost = node.mCost + WAIT_COST
        wait.score = node.score + WAIT_COST
        wait.parent = node
        return wait

    def _expandNode(self,node,end,bids,agentId,conflict):
        nodeRep = (node.lid,node.time)        
        i = self.o.index(nodeRep)
        self.on.pop(i)
        self.o.pop(i)
        self.c.append(nodeRep)
        nodes = self.mh.getAdjacentNodes(node,end,bids,agentId)
#        w = self.generateWaitNode(node)
#        if w != None:
#            nodes.append(w)
        for n in nodes:
            if isConflicted(n,conflict):
                continue                                  
            if n.location == end:
                # reached the destination (Zahy: Returning on generation!!?)                
                return n
            elif (n.lid,n.time) in self.c:
                # already in close, skip this
                continue            
            elif (n.lid,n.time) in self.o:
                # already in open, check if better score
                i = self.o.index((n.lid,n.time))
                on = self.on[i];
                if n.mCost<on.mCost:
                    self.on.pop(i);
                    self.o.pop(i);
                    self.on.append(n);
                    self.o.append((n.lid,n.time));
            else:
                # new node, append to open list
                self.on.append(n);                
                self.o.append((n.lid,n.time));                        
        return None

    def currentPathOrArbitrary(self,solutions,currentPath):
        if currentPath is None or len(solutions)==1:
            return solutions[0]
        for p in solutions:
            if p == currentPath:
                return p
        return solutions[0]
    

    def findPath(self,fromlocation, tolocation,bids,agentId,currentPath,conflict=None):
        self.o = [] #stores (lid and time) pairs
        self.on = [] #stores nodes 
        self.c = []
        solutions = []
        solutionLength = Infinity
        end = tolocation        
        fnode = self.mh.getNode(fromlocation)
        fnode.time=0        
        self.on.append(fnode)
        self.o.append((fnode.lid,fnode.time))
        nextNode = fnode                
        while nextNode is not None: 
            finish = self._expandNode(nextNode,end,bids,agentId,conflict)
            if finish:                
                path = self._tracePath(finish)
                if path.getTotalMoveCost()<=solutionLength:
                    solutions.append(path)
                    solutionLength=path.getTotalMoveCost() 
                else:
                    return self.currentPathOrArbitrary(solutions,currentPath)                                     
            nextNode=self._getBestOpenNode()                
        return solutions[0]
      
      
          
      
class SQ_Location:
    """A simple Square Map Location implementation"""
    def __init__(self,x,y):
        self.x = x
        self.y = y

    def __eq__(self, l):
        """MUST BE IMPLEMENTED"""
        if l.x == self.x and l.y == self.y:
            return 1
        else:
            return 0

class SQ_MapHandler:
    """A simple Square Map implementation"""

    def __init__(self,mapdata,width,height):
        self.m = mapdata
        self.w = width
        self.h = height

    def getNode(self, location):
        """MUST BE IMPLEMENTED"""
        x = location.x
        y = location.y
        if x<0 or x>=self.w or y<0 or y>=self.h:
            return None
        d = self.m[(y*self.w)+x]
        if d == -1:
            return None        
        lid = Lid(((y*self.w)+x),-1)        
        return Node(0,location,d,lid);                

    def getAdjacentNodes(self, curnode, dest,bids,agentId):
        """MUST BE IMPLEMENTED"""        
        result = []
        if isinstance(curnode, EdgeNode):
            result.append(curnode.t)
        else:
            cl = curnode.location
            dl = dest            
            n = self._handleEdgeNode(cl.x+1,cl.y,curnode,dl.x,dl.y,bids,agentId)
            if n: result.append(n)
            n = self._handleEdgeNode(cl.x-1,cl.y,curnode,dl.x,dl.y,bids,agentId)
            if n: result.append(n)
            n = self._handleEdgeNode(cl.x,cl.y+1,curnode,dl.x,dl.y,bids,agentId)
            if n: result.append(n)
            n = self._handleEdgeNode(cl.x,cl.y-1,curnode,dl.x,dl.y,bids,agentId)
            if n: result.append(n)#
            #wait node
            n = self._handleEdgeNode(cl.x,cl.y,curnode,dl.x,dl.y,bids,agentId)
            if n: result.append(n)#
        return result

    
    def _handleEdgeNode(self,x,y,fromnode,destx,desty,bids,agentId):
        trgt = self._expandNode(x, y, fromnode, destx, desty,bids,agentId);
        if trgt is not None:            
            lid = Lid(fromnode.lid.source,trgt.lid.source)   #unique lid            
            n = EdgeNode(fromnode.location,0,lid,fromnode,trgt,fromnode.time+1,fromnode);
            trgt.parent = n
            n.mCost += fromnode.mCost
            penalty = getMaxBid(bids,n.lid,n.time,agentId)
            if penalty>0:                                
                print "penalty for "+str(n.lid)+ "@"+str(n.time)+" is " + str(penalty) 
            n.mCost+=penalty 
            n.score+=penalty            
            trgt.mCost+=penalty # already has the cost of fromNode
            trgt.score+=penalty
            dx = max(x,destx) - min(x,destx)
            dy = max(y,desty) - min(y,desty)
            emCost = dx+dy
            n.score = n.mCost + emCost
            n.parent=fromnode            
            return n
        return None    

    def _expandNode(self,x,y,fromnode,destx,desty,bids,agentId):        
        n = self.getNode(SQ_Location(x,y))
        if n is not None:
            dx = max(x,destx) - min(x,destx)
            dy = max(y,desty) - min(y,desty)
            emCost = dx+dy            
            n.mCost += fromnode.mCost                                   
            n.score = n.mCost+emCost
            n.parent=fromnode
            n.time = fromnode.time+2
            if len(bids)>0:
                penalty = getMaxBid(bids,n.lid,n.time,agentId)
                if penalty>0:
                    print "penalty for "+str(n.lid)+ "@"+str(n.time)+" is " + str(penalty)                
                n.mCost+=penalty 
                n.score+=penalty
            return n
        return None    


    